package com.java.leedcode.链表;

/**
 * @desc: https://leetcode-cn.com/problems/reverse-linked-list/
 * 讲解：https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
 * 图解：https://leetcode-cn.com/problems/reverse-linked-list/solution/yi-bu-yi-bu-jiao-ni-ru-he-yong-di-gui-si-67c3/
 * 视频：https://leetcode-cn.com/problems/reverse-linked-list/solution/shi-pin-jiang-jie-die-dai-he-di-gui-hen-hswxy/
 * @author: zhanghongqiang01@baijiahulian.com
 * @date: 2021/8/22/0022 下午 10:51
 */
public class _206_反转链表 {

    /**
     * 递归
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        /*递的过程-往下钻，头结点和其他结点*/
        //递归终止条件是当前为空，或者下一个节点为空
        if(head==null || head.next==null) {
            return head;
        }
        //这里的newHead就是最后一个节点
        ListNode newHead = reverseList(head.next);
        //如果链表是 1->2->3->4->5，那么此时的newHead就是5
        //而head是4，head的下一个是5，下下一个是空
        //所以head.next.next 就是5->4

        /*归的过程-反转*/
        head.next.next = head;
        //防止链表循环，需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回newHead，也就是最后一个节点
        return newHead;
    }

    /**
     *非递归-头插法
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        /*递的过程-往下钻，头结点和其他结点*/
        //递归终止条件是当前为空，或者下一个节点为空
        if (head == null || head.next == null) {
            return head;
        }

        ListNode newnode = null;
        while (head !=null){
            ListNode temp = head.next;
            head.next = newnode ;
            newnode = head;
            head = temp;
        }

        return newnode;
    }

}
